/* 排序算法 */

#include <stdlib.h>
#include <string.h>

#include "sort.h"



/* 冒泡排序 */
void bubble_sort(int *data, int size)
{
    int i  = 0;
    int j  = 0;

    for(i=0; i<size-1; i++)
    {
        int ordered = 1;

        for(j=0; j<size-1-i; j++)
        {
            if(data[j+1] < data[j])
            {
                int swap = data[j];
                data[j] = data[j+1];
                data[j+1] = swap;

                ordered = 0;
            }
        }
        if(ordered)
        {
            break;
        }
    }
}


/* 插入排序 
 *
 *使首个元素有序

 *依次使前2 3 4 5 6 7个元素有序
 * */
void insert_sort(int *data, int size)
{
    int i  = 0;
    int j = 0;
    for(i=1; i<size;i++)
    {
        int inserted = data[i];
        
        for(j=i; j>0; j--)
        {   
            /*大于被取出数者后移*/
            if(inserted < data[j-1])
            {
                data[j] = data[j-1];
            }
            else
            {
                break;
            }
        }
        if(j != i)
        {
            /*取出元素插入合适位置*/
            data[j] = inserted;
        }
    }
}


/* 选择排序 
 *找出最小的放在首个位置
 *找出次小放在第二个位置
 *......
 *
 * */

void select_sort(int *data, int size)
{
    int i = 0;

    for(i=0; i<size-1; i++)
    {
        int min = i;

        int j = 0;
        for(j=i+1; j<size; j++)
        {
            if(data[j]< data[min])
            {
                min = j;
            }

        }
        
        if(min != i)
        {
            int swap = data[i];
            data[i] = data[min];
            data[min] = swap;
            
        }
    }
}

/* 快速排序 */

void quick_sort(int data[], int left, int right)
{
    int p = (left + right)/2;
    int pivot = data[p];

    int i = left;
    int j = right;
    while(i<j)
    {
            for(; i<p && pivot>=data[i]; i++);

            if(i < p)
            {
                data[p] = data[i];
                p = i;
            }

            for(; j>p && pivot<=data[j]; j--);

            if(j>p)
            {
                data[p] = data[j];
                p = j;
            }
    }

    data[p] = pivot;

    if(p - left > 1)
    {
        quick_sort(data,left, p-1);
    }

    if(right-p > 1)
    {
        quick_sort(data, p+1, right);
    }
}

/* 外部合并 */
static void outer_merge(int data1[], int size1, int data2[], int size2, int data3[])
{
     int i = 0;
     int j= 0;
     int k=0;

    while(1)
    {
        if(i<size1 & j<size2)
        {
            if(data2[j]<data1[i])
            {
                data3[k++] = data2[j++];
            }
            else
            {
                data3[k++] = data1[i++];
            }
        }
        else if(i < size1)
        {
            data3[k++] = data1[i++];
        }
        else if(j < size2)
        {
            data3[k++] = data2[j++];
        }
        else
        {
            break;
        }
    }

}


/* 内部合并 */
static void inner_merge(int data[], int left, int mid, int right)
{
    int size = (right - left + 1) * sizeof(int);
    
    int *merge = malloc(size);

    outer_merge(data+left, mid-left+1, data+mid+1, right-mid, merge);

    memcpy(data+left, merge, size);

    free(merge);
}

/* 归并排序 */
void merge_sort(int data[], int left, int right)
{
    if(left < right)
    {
        int mid = (left + right) /2;

        merge_sort(data, left, mid);
        merge_sort(data, mid+1, right);

        inner_merge(data, left, mid, right);
    }
}
